The present invention relates to the field of logic design as particularly directed toward its implementation in digital computers using binary logic. More particularly, the present invention is directed toward the implementation of Galois logic using binary logic devices that operate according to well-known Boolean algebra.
Galois theory includes the study of finite fields first considered by the 19th Century French mathemetician E. Galois. Since 1948, Galois theory has been applied widely to communication theory where it has led to efficient error-correcting codes. In 1969, in the publication "A Transform for Logic Networks," IEEE Transactions on Computers, Volume C-18, No. 3, March, 1969, K. S. Menger, Jr., established a theorem making the use of the Galois theory applicable to network synthesis. Somewhat later, in 1971, in the publication "A Cellular-Array Multiplier for GF(2.sup.m)," B. A. Laws, Jr., et al, IEEE Transactions on Computers, December, 1971, Pages 1573-1578, there are discussed circuits for calculating the product of two elements of the Galois field GF(2.sup.m) using combinatorial logic.
In Publication I, "Galois Logic Design," J. T. Ellison, et al, AFCRL-70-0583, obtainable from Data Sciences Laboratory, Air Force Cambridge Research Laboratories, Air Force Systems Command, United States Air Force, Bedford, Massachusetts, 01730, there is disclosed a generalized method for the construction of GF(2.sup.n) Galois multipliers, or multiplication gates, using GF(2.sup.1) Galois multipliers, i.e., two-input AND gates, and an Exclusive-OR network for each of the n outputs. This Galois GF(2.sup.n) multiplication gate generates the Galois product EQU X.multidot.Y=(X.multidot.Y).sub.0, . . . , (X.multidot.Y).sub.n-1
from the Galois input on n, X input lines EQU X.sub.0, . . . , X.sub.n-1
and from the Galois input on n, Y input lines EQU Y.sub.0, . . . , Y.sub.n-1.
In the J. T. Ellison Pat. No. 3,805,037 the Galois multiplication gate is converted into a Galois linear gate by the addition of n, Z input lines, each one coupled by a two-input Exclusive-OR gate, to an associated one of an n-output Exclusive-OR network or gate. It is to be appreciated that k-input Exclusive-OR gates, where k is a positive integer of 3 or greater, are synonymous to k-input parity gates, and may be comprised of the number (k-1) of two-input Exclusive-OR gates--see the text "Digital Design," Wiley, Interscience, 1971, R. K. Richards, Pages 198-200.
In Publication II, "Sequential Galois Multipliers," J. M. Marver, Report No. PX 12344, August, 1977, prepared under Contract No. N00014-77-C-0192, with the Office of Naval Research, there has been proposed the construction of Galois multiplication gates having the Galois field GF(2.sup.n) from Galois multiplication gates having the Galois field GF(2.sup.m) where m is a positive integral divisor of n, i.e., k=(n/m). For example, using this proposed technique, it is possible to generate Galois multiplication gates for the Galois field GF(2.sup.8) from Galois multiplication gates for the Galois fields GF(2.sup.1), GF(2.sup.2) or GF(2.sup.4).